package Lab02.Q9;

public class quickSort {
    public static int[] sort(int[] arr) {
        if (arr.length == 0)
            return arr;
        else if (arr.length > 0)
            qsort(arr, 0, arr.length - 1);
        else
            return null;
        return arr;
    }

    public static void qsort(int[] arr, int low, int high) {
        int i = low, j = high;
        if (i > j)
            return;
        int k = arr[i];
        while (i < j) {//哨兵移动
            while (i < j && arr[j] > k)
                j--;
            while (i < j && arr[i] <= k)
                i++;
            if (i < j) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
            k = arr[i];
            arr[i] = arr[low];
            arr[low] = k;
            qsort(arr, low, i - 1);
            qsort(arr, i + 1, high);
        }
    }
}
